

//53. 最大子数组和
//给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

//示例:
//输入: [-2,1,-3,4,-1,2,1,-5,4],
//输出: 6
//解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
//进阶:
//如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。


var maxSubArray = function(nums) {
    // let max = nums[0]
    // let sum = 0
    // for(let i = 0; i < nums.length; i++){
    //     sum += nums[i]
    //     if(sum > max){
    //         max = sum
    //     }
    //     if(sum < 0){
    //         sum = 0
    //     }
    // }
    // return max

  // 分治法
  let dp = new Array(nums.length).fill(0) // 初始化dp数组 dp[i]表示以nums[i]结尾的最大子数组和
  dp[0] = nums[0]   // 初始化第一个元素
  let max = dp[0]     // 初始化最大值
  for(let i = 1; i < nums.length; i++){
      dp[i] = Math.max(dp[i-1] + nums[i], nums[i])  // 当前元素为dp[i-1] + nums[i] 或者 nums[i]
      if(dp[i] > max){  // 如果当前元素大于max，则更新max
          max = dp[i]
      }
  }
  return max
};
let arr = [-2,1,-3,4,-1,2,1,-5,4];
console.log(maxSubArray(arr));